递归和循环

[TOC]

1.斐波那契数列

1.1题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39

1.2解法

// 15ms 5568
function fibonacci(n)
{
    let a=0,b=1;
    if(n==0||n==1){
        return n;
    }
    else{
        while(--n){
            b+=a;
            a=b-a;
        }
        return b;
    }
}

// 递归次数太多
function fibo(n){
    if(n==0||n==1){
        return n;
    }
    return fibo(n-1)+fibo(n-2);
}

function fibonacci(n) {
    if(n===0) return n;
    let [a,b] = [0,1];
    for(let i = 0; i < n - 1; i++){
        [a,b] = [b,a+b];
    }
    return b;
}

2.跳台阶

2.1题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

2.2解法

设f(n)为青蛙跳上一个n级的台阶总共的跳法，那么

如果第一次跳了1阶，那么剩下n-1阶;

如果第一次跳了2阶，那么剩下n-2阶;

于是，f(n)=f(n-1)+f(n-2)。

function jumpFloor(number)
{
    if(number==1) return 1;
    let arr=[1,1];
    for(let i=2;i<=number;i++){
        arr[i]=arr[i-1]+arr[i-2];
    }
    return arr[number];
}

function jump(n){
    if(n==1||n==2){
        return n;
    }
    return jump(n-1)+jump(n-2);
}

3.变态跳台阶

1.1题目描述3

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

3.2解法

设f(n)为n个台阶总共的跳法，即

n=1时，f(1)=1;

n=2时，f(2)=f(2-1)+f(2-2) //f(2-1)：第一次跳了1阶，还剩2-1阶

……

f(n)=f(n-1)+f(n-2)+……+f(n-n)=f(0)+f(1)+……f(n-1)=f(n-1)+f(n-1)

f(n)=2*f(n-1)

function jumpFloorII(number)
{
    // a<<b=a*(2^b)
    return 1<<(--number);
}

4.矩形覆盖

4.1题目描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

4.2解法

可以通过画图来找规律

我的理解是：

设f(n)为n种方法，而摆放的方式实际上只有横摆和竖摆的区别；

最开始先横摆，那么就有f(n-1)种方法；

最开始先竖摆，那么下一步就一定要一个对应的竖摆，就有f(n-2)种方法；

于是，f(n)=f(n-1)+f(n-2)。

function rectCover(number)
{
    if(number<1) return 0;
    if(number==1) return 1;
    let arr=[1,1];
    for(let i=2;i<=number;i++){
        arr[i]=arr[i-1]+arr[i-2];
    }
    return arr[number];
}